#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Solution
{
public:
    int cnt1(int n)
    {
        int cnt = 0;
        while (n)
        {
            n = n & (n - 1), cnt++;
        }
        return cnt;
    }
    bool cmp(int a, int b)
    {
        return cnt1(a) != cnt1(b) ? cnt1(a) < cnt1(b) : a < b;
    }
    void Qsort(vector<int> &arr, int l, int r)
    {
        if (l >= r)
            return;
        swap(arr[(l + r) / 2], arr[r]);
        int pivot = arr[r], i = l - 1;
        for (int j = l; j <= r; ++j)
        {
            if (cmp(arr[j], pivot) == true)
                swap(arr[++i], arr[j]);
        }
        swap(arr[i + 1], arr[r]);
        Qsort(arr, l, i);
        Qsort(arr, i + 2, r);
    }
    vector<int> sortByBits(vector<int> &arr)
    {
        Qsort(arr, 0, arr.size() - 1);
        return arr;
    }
};